<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(C卷,200分)- 伐木工（Java & JS & Python & C & C++）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>一根X米长的树木&#xff0c;伐木工切割成不同长度的木材后进行交易&#xff0c;交易价格为每根木头长度的乘积。规定切割后的每根木头长度都为正整数&#xff1b;也可以不切割&#xff0c;直接拿整根树木进行交易。</p> 
<p>请问伐木工如何尽量少的切割&#xff0c;才能使收益最大化&#xff1f;</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>木材的长度&#xff08;X ≤ 50&#xff09;</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>输出最优收益时的各个树木长度&#xff0c;以空格分隔&#xff0c;按升序排列</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">10</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">3 3 4</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;"> <p>一根2米长的树木&#xff0c;伐木工不切割&#xff0c;为2 * 1&#xff0c;收益最大为2</p> <p>一根4米长的树木&#xff0c;伐木工不需要切割为2 * 2&#xff0c;省去切割成本&#xff0c;直接整根树木交易&#xff0c;为4 * 1&#xff0c;收益最大为4</p> <p>一根5米长的树木&#xff0c;伐木工切割为2 * 3&#xff0c;收益最大为6</p> <p>一根10米长的树木&#xff0c;伐木工可以切割方式一&#xff1a;3&#xff0c;4&#xff0c;3&#xff0c;也可以切割为方式二&#xff1a;3&#xff0c;2&#xff0c;2&#xff0c;3&#xff0c;但方式二伐木工多切割一次&#xff0c;增加切割成本却买了一样的价格&#xff0c;因此并不是最优收益。</p> </td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题可以使用动态规划求解。</p> 
<p></p> 
<ul><li>长度为1的木材&#xff0c;无法切割&#xff0c;只能整个售卖&#xff0c;此时最大收益为1。<br />  </li><li>长度为2的木材&#xff1a;<br /><br /> ①&#xff1a;不切割的话&#xff0c;整个售卖的收益为2&#xff1b;<br /><br /> ②&#xff1a;切割的话&#xff0c;只能分成[1, 1]&#xff0c;此时收益为1*1&#61;1&#xff1b;<br /><br /> 因此最大收益为2。<br />  </li><li>长度为3的木材&#xff1a;<br /><br /> ①&#xff1a;不切割的话&#xff0c;整个售卖的收益为3<br /><br /> ②&#xff1a;切割话&#xff0c;分成两份的话&#xff0c;方案有 [1, 2]&#xff0c;[2, 1]&#xff0c;如果想要分成更多份&#xff0c;此时可以借助之前的状态&#xff0c;比如切割方案[1, 2] 得到一个长度1&#xff0c;一个长度2的木材&#xff0c;而长度1和长度2的木材的最大收益之前已经求解过了&#xff0c;因此此时可以直接复用&#xff0c;而不是重新计算。<br /><br /> 因此很容易得出一个状态转移关系&#xff1a;<br /><br /> dp[i] &#61; max(dp[i], dp[j] &#43; dp[i - j])<br /><br /> 不切割时的收益&#xff1a; dp[i] &#61; i<br /><br /> 切割时的收益&#xff1a;dp[i] &#61; dp[j] &#43; dp[i - j]&#xff0c;含义是&#xff1a;长度 i 的木材至少可以切割为2份&#xff0c;此时我们可以遍历 1~i-1 的长度作为其中一个切割子份 j&#xff0c;而另一个切割子份就是 i - j&#xff0c;而 j 或者 i - j 可以复用之前求解出来dp[j] 和 dp[i - j] 获得对应长度木材的最大收益</li><li>更大的长度&#xff0c;参考长度3的木材</li></ul> 
<p></p> 
<p>但是本题并不是要我们求解木材x的最大收益&#xff0c;而是最大收益条件下的切割状态&#xff0c;此时我们只需要让 dp[i] 除了记录最大收益外&#xff0c;还要记录最大收益对应的切割状态&#xff0c;即 dp[i] 应该设计为一个对象&#xff0c;对象属性如下&#xff1a;</p> 
<ul><li>profit&#xff1a;记录最大收益</li><li>slices&#xff1a;记录最大收益对应的切割状态</li></ul> 
<p>比如初始时&#xff0c;长度 i 的木材如果选择不切割的话&#xff0c;那么</p> 
<blockquote> 
 <p>dp[i] &#61; <br /> {<!-- --><br />    profit: i,<br />    slices: [i]<br /> }</p> 
</blockquote> 
<p>即此时长度 i 木材的收益为 i&#xff0c;切割状态为 [i]&#xff0c;即未发生切割&#xff0c;只有一个木材&#xff0c;就是 i 本身。</p> 
<p></p> 
<p>后续长度 i 的木材选择切割的话&#xff0c;则收益为 slice_profit &#61; dp[j].profit &#43; dp[i - j].profit</p> 
<p>我们需要比较 slice_profit 和 dp[i].profit&#xff0c;如果slice_profit更大&#xff0c;则需要更新dp[i]的</p> 
<ul><li>profit &#61; slice_profit</li><li>slices &#61; dp[j].slices &#43; dp[i-j].slices</li></ul> 
<p>如果slice_profit 和 dp[i].profit二者收益相同&#xff0c;则需要进一步比较当前dp[i].slices切割状态的份数&#xff0c;和&#xff08;dp[j].slices的份数 &#43; dp[i-j].slices的份数&#xff09;&#xff0c;看哪个更少&#xff0c;更少的更优&#xff0c;然后更新dp[i]为更少的那个方案。</p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JS算法源码</h4> 
<pre><code class="language-javascript">const rl &#61; require(&#34;readline&#34;).createInterface({ input: process.stdin });
var iter &#61; rl[Symbol.asyncIterator]();
const readline &#61; async () &#61;&gt; (await iter.next()).value;

class Wood {
  constructor(profit, slices) {
    this.profit &#61; profit; // 记录木材的最大收益
    this.slices &#61; slices; // 记录木材最大收益时对应的切割状态
  }
}

void (async function () {
  const x &#61; parseInt(await readline());

  const dp &#61; new Array(x &#43; 1);

  for (let i &#61; 0; i &lt;&#61; x; i&#43;&#43;) {
    // 初始时&#xff0c;将木材不切割的收益作为最大收益
    dp[i] &#61; new Wood(i, [i]);
  }

  // 从长度为2的木材开始尝试切割
  for (let i &#61; 2; i &lt;&#61; x; i&#43;&#43;) {
    for (let j &#61; 1; j &lt; i; j&#43;&#43;) {
      const profit &#61; dp[j].profit * dp[i - j].profit;

      // 如果该切割方案的收益更大&#xff0c;或者收益和之前切割方案的收益相同&#xff0c;但是切割数更少&#xff0c;则使用当前切割方案
      if (
        profit &gt; dp[i].profit ||
        (profit &#61;&#61; dp[i].profit &amp;&amp;
          dp[i].slices.length &gt; dp[j].slices.length &#43; dp[i - j].slices.length)
      ) {
        dp[i].profit &#61; profit;
        dp[i].slices &#61; [...dp[j].slices, ...dp[i - j].slices];
      }
    }
  }

  // dp[x].slices记录的是&#xff1a;长度x的木材对应的最大收益的切割方案
  // 按题目输出描述要求进行升序
  const res &#61; dp[x].slices.sort((a, b) &#61;&gt; a - b).join(&#34; &#34;);

  // 打印切割方案
  console.log(res);
})();
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.ArrayList;
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {
  static class Wood {
    int profit; // 记录木材的最大收益
    ArrayList&lt;Integer&gt; slices &#61; new ArrayList&lt;&gt;(); // 记录木材最大收益时对应的切割状态
  }

  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);
    int x &#61; sc.nextInt();

    Wood[] dp &#61; new Wood[x &#43; 1];

    for (int i &#61; 0; i &lt;&#61; x; i&#43;&#43;) {
      // 初始时&#xff0c;将木材不切割的收益作为最大收益
      dp[i] &#61; new Wood();
      dp[i].profit &#61; i;
      dp[i].slices.add(i);
    }

    // 从长度为2的木材开始尝试切割
    for (int i &#61; 2; i &lt;&#61; x; i&#43;&#43;) {
      for (int j &#61; 1; j &lt; i; j&#43;&#43;) {
        int profit &#61; dp[j].profit * dp[i - j].profit;

        // 如果该切割方案的收益更大&#xff0c;或者收益和之前切割方案的收益相同&#xff0c;但是切割数更少&#xff0c;则使用当前切割方案
        if (profit &gt; dp[i].profit
            || (profit &#61;&#61; dp[i].profit
                &amp;&amp; dp[i].slices.size() &gt; dp[j].slices.size() &#43; dp[i - j].slices.size())) {
          dp[i].profit &#61; profit;
          dp[i].slices.clear();
          dp[i].slices.addAll(dp[j].slices);
          dp[i].slices.addAll(dp[i - j].slices);
        }
      }
    }

    // dp[x].slices记录的是&#xff1a;长度x的木材对应的最大收益的切割方案
    // 按题目输出描述要求进行升序
    dp[x].slices.sort((a, b) -&gt; a - b);

    // 打印切割方案
    StringJoiner sj &#61; new StringJoiner(&#34; &#34;);
    for (int slice : dp[x].slices) {
      sj.add(slice &#43; &#34;&#34;);
    }

    System.out.println(sj);
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python">class Wood:
    def __init__(self, profit, slices):
        self.profit &#61; profit
        self.slices &#61; slices


# 输入获取
x &#61; int(input())


# 算法入口
def getResult():
    # 初始时&#xff0c;将木材不切割的收益作为最大收益&#xff0c;即长度i的木头&#xff0c;不切割时&#xff0c;收益为i&#xff0c;切割方案为[i]
    dp &#61; [Wood(i, [i]) for i in range(x &#43; 1)]

    # 从长度为2的木材开始尝试切割
    for i in range(2, x &#43; 1):
        for j in range(1, i):
            profit &#61; dp[j].profit * dp[i - j].profit

            # 如果该切割方案的收益更大&#xff0c;或者收益和之前切割方案的收益相同&#xff0c;但是切割数更少&#xff0c;则使用当前切割方案
            if profit &gt; dp[i].profit or (profit &#61;&#61; dp[i].profit and len(dp[i].slices) &gt; len(dp[j].slices) &#43; len(dp[i - j].slices)):
                dp[i].profit &#61; profit
                dp[i].slices.clear()
                dp[i].slices.extend(dp[j].slices)
                dp[i].slices.extend(dp[i - j].slices)

    # dp[x].slices记录的是&#xff1a;长度x的木材对应的最大收益的切割方案
    # 按题目输出描述要求进行升序
    dp[x].slices.sort()

    return &#34; &#34;.join(map(str, dp[x].slices))


# 算法调用
print(getResult())
</code></pre> 
<p></p> 
<h4>C算法源码</h4> 
<pre><code class="language-cpp">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

#define MAX_SIZE 50

typedef struct Wood {
    int profit; // 记录木材的最大收益
    int slices[MAX_SIZE]; // 记录木材最大收益时对应的切割状态
    int slices_size; // 记录木材最大收益时对应的切割次数
} Wood;

int cmp(const void *a, const void *b) {
    return *((int *) a) - *((int *) b);
}

int main() {
    int x;
    scanf(&#34;%d&#34;, &amp;x);

    Wood *dp[x &#43; 1];
    for (int i &#61; 0; i &lt;&#61; x; i&#43;&#43;) {
        dp[i] &#61; (Wood *) malloc(sizeof(Wood));
        // 初始时&#xff0c;将木材不切割的收益作为最大收益
        dp[i]-&gt;profit &#61; i;
        dp[i]-&gt;slices[0] &#61; i;
        dp[i]-&gt;slices_size &#61; 1;
    }

    // 从长度为2的木材开始尝试切割
    for (int i &#61; 2; i &lt;&#61; x; i&#43;&#43;) {
        for (int j &#61; 1; j &lt; i; j&#43;&#43;) {
            int profit &#61; dp[j]-&gt;profit * dp[i - j]-&gt;profit;

            // 如果该切割方案的收益更大&#xff0c;或者收益和之前切割方案的收益相同&#xff0c;但是切割数更少&#xff0c;则使用当前切割方案
            if (profit &gt; dp[i]-&gt;profit ||
                (profit &#61;&#61; dp[i]-&gt;profit &amp;&amp; dp[i]-&gt;slices_size &gt; dp[j]-&gt;slices_size &#43; dp[i - j]-&gt;slices_size)) {
                dp[i]-&gt;profit &#61; profit;

                dp[i]-&gt;slices_size &#61; dp[j]-&gt;slices_size &#43; dp[i - j]-&gt;slices_size;

                int m &#61; 0;
                for (; m &lt; dp[j]-&gt;slices_size; m&#43;&#43;) { // 注意这里是dp[j]-&gt;slices_size
                    dp[i]-&gt;slices[m] &#61; dp[j]-&gt;slices[m];
                }

                for (int n &#61; 0; n &lt; dp[i - j]-&gt;slices_size; n&#43;&#43;) { // 注意这里是dp[i-j]-&gt;slices_size
                    dp[i]-&gt;slices[n &#43; m] &#61; dp[i - j]-&gt;slices[n];
                }
            }
        }
    }

    // dp[x].slices记录的是&#xff1a;长度x的木材对应的最大收益的切割方案
    // 按题目输出描述要求进行升序
    qsort(dp[x]-&gt;slices, dp[x]-&gt;slices_size, sizeof(int), cmp);

    // 打印切割方案
    for (int i &#61; 0; i &lt; dp[x]-&gt;slices_size; i&#43;&#43;) {
        printf(&#34;%d&#34;, dp[x]-&gt;slices[i]);

        if (i &lt; dp[x]-&gt;slices_size - 1) {
            printf(&#34; &#34;);
        }
    }

    return 0;
}</code></pre> 
<p></p> 
<h4>C&#43;&#43;算法源码</h4> 
<pre><code class="language-cpp">#include &lt;bits/stdc&#43;&#43;.h&gt;

using namespace std;

class Wood {
public:
    int profit{}; // 记录木材的最大收益
    vector&lt;int&gt; slices;
};

int main() {
    int x;
    cin &gt;&gt; x;

    Wood dp[x &#43; 1];
    for (int i &#61; 0; i &lt;&#61; x; i&#43;&#43;) {
        // 初始时&#xff0c;将木材不切割的收益作为最大收益
        dp[i].profit &#61; i;
        dp[i].slices.emplace_back(i);
    }

    // 从长度为2的木材开始尝试切割
    for (int i &#61; 2; i &lt;&#61; x; i&#43;&#43;) {
        for (int j &#61; 1; j &lt; i; j&#43;&#43;) {
            int profit &#61; dp[j].profit * dp[i - j].profit;

            // 如果该切割方案的收益更大&#xff0c;或者收益和之前切割方案的收益相同&#xff0c;但是切割数更少&#xff0c;则使用当前切割方案
            if (profit &gt; dp[i].profit ||
                (profit &#61;&#61; dp[i].profit &amp;&amp; dp[i].slices.size() &gt; dp[j].slices.size() &#43; dp[i - j].slices.size())) {
                dp[i].profit &#61; profit;
                dp[i].slices.clear();

                for (const auto &amp;item: dp[j].slices) {
                    dp[i].slices.emplace_back(item);
                }

                for (const auto &amp;item: dp[i - j].slices) {
                    dp[i].slices.emplace_back(item);
                }
            }
        }
    }

    // dp[x].slices记录的是&#xff1a;长度x的木材对应的最大收益的切割方案
    // 按题目输出描述要求进行升序
    sort(dp[x].slices.begin(), dp[x].slices.end());

    // 打印切割方案
    for (const auto &amp;item: dp[x].slices) {
        cout &lt;&lt; item &lt;&lt; &#34; &#34;;
    }
    cout &lt;&lt; endl;

    return 0;
}</code></pre> 
<p></p>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>